<!DOCTYPE html>
<html lang=zh-CN>
<head>
<meta charset=utf-8>
<title>算法: 三只水桶等分水问题 | Cweili Beta</title>
<meta name=viewport content="width=device-width,initial-scale=1,maximum-scale=1,user-scalable=no">
<meta name=description content="有一个容积为 8 升的水桶里装满了水，另外还有一个容积为 3 升的空桶和一个容积为 5 升的空桶，如何利用这两个空桶等分 8 升水？附加条件是三个水桶都没有体积刻度，也不能使用其它辅助容器。
这是一道经典题目，一般人都可以在一分钟内给出答案，不过，很多人可能没有注意到这道题的答案不是唯一的。先来看看最常见的一个答案，也是目前已知最快的操作步骤，共需要 7 次倒水动作：">
<meta property=og:type content=article>
<meta property=og:title content="算法: 三只水桶等分水问题">
<meta property=og:url content="http://cweili.gitcafe.com/algorithm-pour-three-buckets/">
<meta property=og:site_name content="Cweili Beta">
<meta property=og:description content="有一个容积为 8 升的水桶里装满了水，另外还有一个容积为 3 升的空桶和一个容积为 5 升的空桶，如何利用这两个空桶等分 8 升水？附加条件是三个水桶都没有体积刻度，也不能使用其它辅助容器。
这是一道经典题目，一般人都可以在一分钟内给出答案，不过，很多人可能没有注意到这道题的答案不是唯一的。先来看看最常见的一个答案，也是目前已知最快的操作步骤，共需要 7 次倒水动作：">
<meta property=og:image content=http://cweili-wordpress.stor.sinaapp.com/uploads/algorithm-pour-three-buckets-1.gif>
<meta property=og:image content=http://cweili-wordpress.stor.sinaapp.com/uploads/algorithm-pour-three-buckets-2.gif>
<meta name=twitter:card content=summary>
<meta name=twitter:title content="算法: 三只水桶等分水问题">
<meta name=twitter:description content="有一个容积为 8 升的水桶里装满了水，另外还有一个容积为 3 升的空桶和一个容积为 5 升的空桶，如何利用这两个空桶等分 8 升水？附加条件是三个水桶都没有体积刻度，也不能使用其它辅助容器。
这是一道经典题目，一般人都可以在一分钟内给出答案，不过，很多人可能没有注意到这道题的答案不是唯一的。先来看看最常见的一个答案，也是目前已知最快的操作步骤，共需要 7 次倒水动作：">
<link rel=alternative href=/atom.xml title="Cweili Beta" type=application/atom+xml>
<link rel=icon href=favicon.png>
<link rel=stylesheet href=//libs.baidu.com/bootstrap/3.2.0/css/bootstrap.min.css type=text/css>
<link rel=stylesheet href=../css/style.css type=text/css>
<!--[if lt IE 9]><script src="//cdn.staticfile.org/html5shiv/3.7/html5shiv.min.js" type="text/javascript"></script><![endif]-->
</head>
<body>
<div id=container>
<nav id=mobile-nav class=visible-xs>
<a href="/" class=mobile-nav-link>首页</a>
<ul class=category-list><li class=category-list-item><a class=category-list-link href=../category/学习笔记>学习笔记</a><span class=category-list-count>40</span></li><li class=category-list-item><a class=category-list-link href=../category/小生活>小生活</a><span class=category-list-count>27</span></li><li class=category-list-item><a class=category-list-link href=../category/杂物>杂物</a><span class=category-list-count>9</span></li></ul>
<a href="/tag/%E7%9B%B8%E5%86%8C/" class=mobile-nav-link>相册</a>
<a href="/about/" class=mobile-nav-link>关于</a>
<div class=clearfix></div>
</nav>
<div id=wrap>
<!--[if lt IE 9]><p class="browsehappy alert alert-danger">您正在使用一个<strong>过时</strong>的浏览器。请<a href="http://browsehappy.com/" target="_blank">更新您的浏览器</a>来达到更好的体验。</p><![endif]-->
<header id=header>
<div id=banner></div>
<div id=header-outer class=outer>
<div id=header-inner class=inner>
<nav class=main-nav>
<div id=main-nav-toggle class="nav-icon visible-xs"><i class="fa fa-bars"></i></div>
<a class="main-nav-link hidden-xs" href="/">首页</a>
</nav>
<nav id=category-nav class=hidden-xs>
<ul class=category-list><li class=category-list-item><a class=category-list-link href=../category/学习笔记>学习笔记</a><span class=category-list-count>40</span></li><li class=category-list-item><a class=category-list-link href=../category/小生活>小生活</a><span class=category-list-count>27</span></li><li class=category-list-item><a class=category-list-link href=../category/杂物>杂物</a><span class=category-list-count>9</span></li></ul>
</nav>
<nav class="main-nav hidden-xs">
<a class=main-nav-link href="/tag/%E7%9B%B8%E5%86%8C/">相册</a>
<a class=main-nav-link href="/about/">关于</a>
</nav>
<nav id=sub-nav>
<a id=nav-rss-link class="nav-icon pull-right hidden-xs" href=/atom.xml title="RSS 订阅"><i class="fa fa-rss"></i></a>
<div id=nav-search-btn class="nav-icon pull-right" title=搜索><i class="fa fa-search"></i></div>
</nav>
<div id=search-form-wrap>
<form action=http://www.baidu.com/baidu accept-charset=utf-8 class=search-form target=_blank>
<input type=search name=word class=search-form-input placeholder=搜索>
<input id=search-form-submit type=submit value=&nbsp; class=search-form-submit>
<input name=tn type=hidden value=bds>
<input name=cl type=hidden value=3>
<input name=ct type=hidden value=2097152>
<input type=hidden name=si value=cweili.gitcafe.com>
<label class=search-form-submit for=search-form-submit><i class="fa fa-search"></i></label>
</form>
</div>
</div>
<div id=header-title class=inner>
<h1 id=logo-wrap>
<a href="/" id=logo>Cweili Beta</a>
</h1>
<h2 id=subtitle-wrap>
<a href="/" id=subtitle>I&#39;m working on it</a>
</h2>
</div>
</div>
</header>
<div class=outer>
<section id=main class=col-sm-9><article id=post-algorithm-pour-three-buckets class="article article-type-post" itemscope itemprop=blogPost>
<div class=article-meta>
<a href="/algorithm-pour-three-buckets/" class=article-date>
<time datetime=2011-11-05T09:45:39.000Z itemprop=datePublished>2011-11-05</time>
</a>
<div class=article-category>
<a class=article-category-link href=../category/学习笔记>学习笔记</a>
</div>
</div>
<div class="article-inner jiathis_streak">
<header class=article-header>
<h2 class=article-title itemprop=name>
算法: 三只水桶等分水问题
</h2>
</header>
<div class=article-entry itemprop=articleBody>
<p>有一个容积为 8 升的水桶里装满了水，另外还有一个容积为 3 升的空桶和一个容积为 5 升的空桶，如何利用这两个空桶等分 8 升水？附加条件是三个水桶都没有体积刻度，也不能使用其它辅助容器。</p>
<p>这是一道经典题目，一般人都可以在一分钟内给出答案，不过，很多人可能没有注意到这道题的答案不是唯一的。先来看看最常见的一个答案，也是目前已知最快的操作步骤，共需要 7 次倒水动作：<a id=more></a></p>
<p>从容积是 8 升的桶中倒 5 升水到容积是 5 升的桶中 <br> 从容积是 5 升的桶中倒 3 升水到容积是 3 升的桶中 <br> 从容积是 3 升的桶中倒 3 升水到容积是 8 升的桶中 <br> 从容积是 5 升的桶中倒 2 升水到容积是 3 升的桶中 <br> 从容积是 8 升的桶中倒 5 升水到容积是 5 升的桶中 <br> 从容积是 5 升的桶中倒 1 升水到容积是 3 升的桶中 <br> 从容积是 5 升的桶中倒 3 升水到容积是 8 升的桶中<br>&lt; 结束 &gt;</p>
<p>这里再给出一个稍微复杂一点的答案，这个答案需要 8 次倒水动作：</p>
<p>从容积是 8 升的桶中倒 3 升水到容积是 3 升的桶中 <br> 从容积是 3 升的桶中倒 3 升水到容积是 5 升的桶中 <br> 从容积是 8 升的桶中倒 3 升水到容积是 3 升的桶中 <br> 从容积是 3 升的桶中倒 2 升水到容积是 5 升的桶中 <br> 从容积是 5 升的桶中倒 5 升水到容积是 8 升的桶中 <br> 从容积是 3 升的桶中倒 1 升水到容积是 5 升的桶中 <br> 从容积是 8 升的桶中倒 3 升水到容积是 3 升的桶中 <br> 从容积是 3 升的桶中倒 3 升水到容积是 5 升的桶中<br>&lt; 结束 &gt;</p>
<p>到底有多少种答案呢？这里先卖个关子，耐心看完本文你就知道了。</p>
<h2 id=解决问题的思路>解决问题的思路</h2>
<p>如果用人的思维方式，那么解决这个问题的关键是怎么通过倒水凑出确定的 1 升水或能容纳 1 升水的空间，考察三只水桶的容积分别是 3、5 和 8，用这三个数做加减运算，可以得到很多组答案，例如：</p>
<p>3 – (5 - 3) = 1</p>
<p>这个策略对应了上面提到的第一种解决方法，而另一组运算：</p>
<p>（3 + 3）- 5 = 1</p>
<p>则对应了上面提到的第二种解决方法。</p>
<p>但是计算机并不能理解这个“1”的重要性，很难按照人类的思维方式按部就班地推导答案，因此用计算机解决这个问题，通常会选择使用“穷举法”。为什么使用穷举法？因为这不是一个典型意义上的求解最优解的问题，虽然可以暗含一个求解倒水次数最少的方法的要求，但就本质而言，常用的求解最优解问题的高效的方法都不适用于此问题。如果能够穷举解空间的全部合法解，然后通过比较找到最优解也是一种求解最优解的方法。不过就本题题意而言，并不关心什么方法最快，能求出全部等分水的方法可能更符合题意。</p>
<p>如果我们把某一时刻三个水桶中存水的容积称为一个状态，则问题的初始状态是 8 升的水桶装满水，求解的解出状态（最终状态）是 8 升水桶中 4 升水，5 升水桶中 4 升水。穷举法的实质就是把从初始状态开始，根据某种状态变化的规则搜索全部可能的状态，每当找到一个从初始状态到最终状态的变化路径，就可以理解为找到了一种答案。这样的状态变化搜索的结果通常是得到一棵状态搜索树，根节点是初始状态，叶子节点可能是最终状态，也可能是某个无法转换到最终状态的中间状态，状态树有多少个最终状态的叶子节点，就有多少种答案。根据以上分析结果，解决本问题的算法关键有三点：首先，建立算法的状态模型；其次，确定状态树的搜索算法（暗含状态转换的规则）；最后，需要一些提高算法效率的手段，比如应用“剪枝”条件避免重复的状态搜索，还要避免状态的循环生成导致搜索算法在若干个状态之间无限循环。</p>
<h2 id=状态和动作的数学模型>状态和动作的数学模型</h2>
<p>建立状态模型是整个算法的关键，这个状态模型不仅要能够描述静止状态，还要能够描述并记录状态转换动作，尤其是对状态转换的描述，因为这会影响到状态树搜索算法的设计。所谓的静止状态，就是某一时刻三个水桶中存水的容积，我们采用长度为 3 的一维向量描述这个状态。这组向量的三个值分别是容积为 8 升的桶中的水量、容积为 5 升的桶中的水量和容积为 3 升的桶中的水量。因此算法的初始状态就可以描述为[8 ,0, 0]，则终止状态为[4, 4, 0]。</p>
<p>对状态转换的描述就是在两个状态之间建立关联，在本算法中这个关联就是一个合法的倒水动作。某一时刻三个水桶中的存水状态，经过某个倒水动作后演变到一个新的存水状态，这是对状态转换的文字描述，对算法来讲，倒水状态描述就是“静止状态”＋“倒水动作”。我们用一个三元组来描述倒水动作：{from, to, water}，from 是指从哪个桶中倒水，to 是指将水倒向哪个桶，water 是此次倒水动作所倒的水量。本模型的特例就是第一个状态如何得到，也就是 [8, 0, 0] 这个状态对应的倒水动作如何描述？我们用 -1 表示未知的水桶编号（上帝水桶），因此第一个状态对应的倒水动作就是{-1, 1, 8}。应用本模型对前面提到的第一种解决方法进行状态转换描述，整个过程如图（1）所示：</p>
<p><a href=http://cweili-wordpress.stor.sinaapp.com/uploads/algorithm-pour-three-buckets-1.gif target=_blank rel=external><img src=http://cweili-wordpress.stor.sinaapp.com/uploads/algorithm-pour-three-buckets-1.gif alt=""></a></p>
<p>图 1 一个解决方法的状态转换图</p>
<p>为了算法实现过程中方便数据管理，用 C/C++ 语言描述的倒水动作三元组是一个 struct，定义如下：</p>
<figure class="highlight cpp"><table><tr><td class=gutter><pre><div class=line>1</div><div class=line>2</div><div class=line>3</div><div class=line>4</div><div class=line>5</div></pre></td><td class=code><pre><div class=line><span class=keyword>struct</span> Action {</div><div class=line>	<span class=keyword>int</span> from;</div><div class=line>	<span class=keyword>int</span> to;</div><div class=line>	<span class=keyword>int</span> water;</div><div class=line>};</div></pre></td></tr></table></figure>
<p>Action 数据结构的三个属性分别对应动作三元组中的三个成员。BucketState 是状态模型的 C/C++ 语言描述，一维向量 bucket_s 是三个水桶中水的状态，curAction 是与之对应的倒水动作，在状态模型中增加倒水动作对本题的数学模型来说不是必需的，它的存在只是为了算法结果输出的需要，就是要能够描述并记录状态转换动作。BucketState 的 C/C++ 语言描述如下所示：</p>
<figure class="highlight cpp"><table><tr><td class=gutter><pre><div class=line>1</div><div class=line>2</div><div class=line>3</div><div class=line>4</div><div class=line>5</div><div class=line>6</div></pre></td><td class=code><pre><div class=line><span class=keyword>struct</span> BucketState {</div><div class=line>	......</div><div class=line>	<span class=keyword>int</span> bucket_s[buckets_count];  <span class=comment>/* 状态向量 */</span></div><div class=line>	Action curAction;             <span class=comment>/* 倒水动作 */</span></div><div class=line>	......</div><div class=line>};</div></pre></td></tr></table></figure>
<h2 id=状态树搜索算法>状态树搜索算法</h2>
<p>确定了状态模型后，就需要解决算法面临的第二个问题：状态树的搜索算法。一个静止状态结合不同的倒水动作会迁移到不同的状态，所有状态转换所展示的就是一棵以状态 [8, 0, 0] 为根的状态搜索树，图（2）画出了这个状态搜索树的一部分，其中一个用不同颜色标识出来的状态转换过程（状态树的一个分支）就是本问题的一个解：</p>
<p><a href=http://cweili-wordpress.stor.sinaapp.com/uploads/algorithm-pour-three-buckets-2.gif target=_blank rel=external><img src=http://cweili-wordpress.stor.sinaapp.com/uploads/algorithm-pour-three-buckets-2.gif alt=""></a></p>
<p>图 2 状态树一部分的展示</p>
<p>状态树的搜索就是对整个状态树进行遍历，这中间其实暗含了状态的生成，因为状态树一开始并不完整，只有一个初始状态的根节点，当搜索（也就是遍历）操作完成时，状态树才完整。树的遍历可以采用广度优先遍历算法，也可以采用深度优先遍历算法，就本题而言，要求解所有可能的等分水的方法，暗含了要记录从初始状态到最终状态，所以更适合使用深度优先遍历算法。状态树的遍历暗含了一个状态生成的过程，就是促使状态树上的一个状态向下一个状态转换的驱动过程，这是一个很重要的部分，如果不能正确地驱动状态变化，就不能实现状态树的遍历（搜索）。</p>
<p>建立状态模型一节中提到的动作模型，就是驱动状态变化的关键因子。对一个状态来说，它能转换到哪些新状态，取决于它能应用哪些倒水动作，一个倒水动作能够在原状态的基础上“生成”一个新状态，不同的倒水动作可以“生成”不同的新状态。由此可知，状态树遍历的关键是找到三个水桶之间所有合法的倒水动作，用这些倒水动作分别“生成”各自相应的新状态。遍历三个水桶的所有可能动作，就是对三个水桶任取两个进行全排列（常用的排列组合算法可以参考《排列组合算法》一文），共有 6 种水桶的排列组合，也就是说有 6 种可能的倒水动作。将这 6 种倒水动作依次应用到当前状态，就可以“生成”6 种新状态，从而驱动状态发生变化（有些排列并不能组合出合法的倒水动作，关于这一点后面“算法优化”部分会介绍）。</p>
<h2 id=算法优化和避免状态循环>算法优化和避免状态循环</h2>
<p>从图（2）可以看出来，对于三个水桶这样小规模的题目，其整个状态树的规模也是相当大的，更何况是复杂一点的情况，因此类似本文这样对搜索整个状态树求解问题的算法都不得不面对一个算法效率的问题，必须要考虑如何进行优化，减少一些明显不必要的搜索，加快求解的过程。</p>
<p>前文讲过，状态搜索的核心是对三个水桶进行两两排列组合得到 6 种倒水动作，但是并不是每种倒水动作都是合法的，比如，需要倒出水的桶中没有水的情况和需要倒进水的桶中已经满的情况下，都组合不出合法的倒水动作。除此之外，因为水桶是没有刻度的，因此倒水动作也是受限制的，也就是说合法的倒水动作只能有两种结果：需要倒出水的桶被倒空和需要倒进水的桶被倒满。加上这些限制之后，每次组合其实只有少数倒水动作是合法的，可以驱动当前的状态到下一个状态。利用这一点，就可以对状态树进行“剪枝”，避免对无效（非法）的状态分支进行搜索。</p>
<p>除了通过“剪枝”提高算法效率，对于深度优先的状态搜索还需要防止因状态的循环生成造成深度优先搜索无法终止的问题。状态的循环生成有两种表现形式：一种是在两个桶之间互相倒水；另一种就是图（2）中展示的一个例子，[3, 5, 0] -&gt; [3, 2, 3] -&gt; [6, 2, 0] -&gt; [3, 5, 0]形成一个状态环。要避免出现状态环，就需要记录一次深度遍历过程中所有已经搜索过的状态，形成一个当前搜索已经处理过的状态表，每当生成一个新状态，就先检查是否是状态表中已经存在的状态，如果是则放弃这个状态，回溯到上一步继续搜索。如果新状态是状态表中没有的状态，则将新状态加入到状态表，然后从新状态开始继续深度优先遍历。在这个过程中因重复出现被放弃的状态，可以理解为另一种形式的“剪枝”，可以使一次深度优先遍历很快收敛到初始状态。</p>
<h2 id=算法实现>算法实现</h2>
<p>解决了算法的三个关键点后，剩下的问题就是写出算法了。先看看“剪枝”的实现：</p>
<figure class="highlight cpp"><table><tr><td class=gutter><pre><div class=line>1</div><div class=line>2</div><div class=line>3</div><div class=line>4</div><div class=line>5</div><div class=line>6</div><div class=line>7</div></pre></td><td class=code><pre><div class=line><span class=keyword>bool</span> IsCurrentActionValid(BucketState& current, <span class=keyword>int</span> from, <span class=keyword>int</span> to) {</div><div class=line>	<span class=comment>/* 从 from 到 to 倒水，如果成功，返回倒水后的状态 */</span></div><div class=line>	<span class=keyword>if</span>((from != to) && !current.IsBucketEmpty(from) && !current.IsBucketFull(to) ) {</div><div class=line>		<span class=keyword>return</span> <span class=keyword>true</span>;</div><div class=line>	}</div><div class=line>	<span class=keyword>return</span> <span class=keyword>false</span>;</div><div class=line>}</div></pre></td></tr></table></figure>
<p>正如前文分析的那样，当需要倒出的水桶是空的或需要倒入的水桶已满时，from-&gt;to 就不是合法的倒水动作，当然，任何一个水桶也不能向自身倒水，这个是常识，但是计算机不知道，所以 (from != to) 就是告诉它这样不行。</p>
<p>在状态搜索的过程中需要维护一张已经搜索过的状态列表，算法实现采用 STL::Deque 来组织这个列表。因为搜索算法的关系，这个列表中的状态是有顺序的，并且每个状态数据内部都记录有这个状态对应的倒水动作，所以遍历这个列表就可以知道当前状态是从初始状态经过怎样的一个倒水过程。如果当前状态就是结果状态，就可以根据这个列表输出整个倒水动作序列。PrintResult()函数输出整个倒水动作序列的：</p>
<figure class="highlight cpp"><table><tr><td class=gutter><pre><div class=line>1</div><div class=line>2</div><div class=line>3</div><div class=line>4</div><div class=line>5</div><div class=line>6</div></pre></td><td class=code><pre><div class=line><span class=keyword>void</span> PrintResult(<span class=built_in>deque</span>& states) {</div><div class=line>	<span class=built_in>cout</span> &lt;&lt; <span class=string>"Find Result :"</span> &lt;&lt; endl;</div><div class=line>	for_each(states.begin(), states.end(),</div><div class=line>		mem_fun_ref(&BucketState::PrintStates));</div><div class=line>	<span class=built_in>cout</span> &lt;&lt; endl &lt;&lt; endl;</div><div class=line>}</div></pre></td></tr></table></figure>
<p>PrintStates()函数是 BucketState 的成员函数，负责打印一个状态自身，包括当前桶中水的状态以及倒水动作：</p>
<figure class="highlight cpp"><table><tr><td class=gutter><pre><div class=line>1</div><div class=line>2</div><div class=line>3</div><div class=line>4</div><div class=line>5</div><div class=line>6</div><div class=line>7</div><div class=line>8</div><div class=line>9</div></pre></td><td class=code><pre><div class=line><span class=keyword>void</span> BucketState::PrintStates() {</div><div class=line>	<span class=built_in>cout</span> &lt;&lt; <span class=string>"Dump"</span> &lt;&lt; curAction.water &lt;&lt; <span class=string>"water from"</span></div><div class=line>	&lt;&lt; curAction.from + <span class=number>1</span> &lt;&lt; <span class=string>"to"</span> &lt;&lt; curAction.to + <span class=number>1</span> &lt;&lt; <span class=string>","</span>;</div><div class=line>	<span class=built_in>cout</span> &lt;&lt; <span class=string>"buckets water states is :"</span>;</div><div class=line>	<span class=keyword>for</span>(<span class=keyword>int</span> i = <span class=number>0</span>; i &lt; buckets_count; ++i) {</div><div class=line>		<span class=built_in>cout</span> &lt;&lt; bucket_s[i] &lt;&lt; <span class=string>""</span>;</div><div class=line>	}</div><div class=line>	<span class=built_in>cout</span> &lt;&lt; endl;</div><div class=line>}</div></pre></td></tr></table></figure>
<p>IsProcessedState()函数判断一个状态是否是状态列表中已经存在状态，利用 STL 库的便利，这个函数的实现也很简单：</p>
<figure class="highlight cpp"><table><tr><td class=gutter><pre><div class=line>1</div><div class=line>2</div><div class=line>3</div><div class=line>4</div><div class=line>5</div><div class=line>6</div></pre></td><td class=code><pre><div class=line><span class=keyword>bool</span> IsProcessedState(<span class=built_in>deque</span>& states, <span class=keyword>const</span> BucketState& newState) {</div><div class=line>	deque::iterator it = states.end();</div><div class=line>	it = find_if(states.begin(), states.end(),</div><div class=line>	bind2nd(ptr_fun(IsSameBucketState), newState) );</div><div class=line>	<span class=keyword>return</span> (it != states.end());</div><div class=line>}</div></pre></td></tr></table></figure>
<p>实现了“剪枝”判断函数，又知道了状态列表是以什么形式组织的，剩下的工作就是完成状态树的搜索了。状态树的搜索是一个递归的过程：从初始状态开始，由第一个合法的倒水动作得到一个新的状态，记录这个状态，并从这个新状态开始遍历穷举，穷举完成后（无论是否得到结果），取消这个状态，然后从下一个合法的倒水动作再得到一个新状态，然后从这个状态开始遍历穷举，直到遍历完所有合法的倒水动作。</p>
<p>状态搜索的结束条件是什么？算法的广度搜索结束条件是遍历完所有的合法倒水动作，深度搜索的结束条件有两个：一个是得到最终状态（成功的情况），另一个是从某个状态开始所有合法倒水动作得到的新状态都和与已经遍历过的状态列表中的状态重复（失败的情况）。</p>
<p>SearchState()函数就是状态搜索算法的核心，这个函数首先检查当前状态列表的最后一个状态是否是结果需要的最终状态（[4, 4, 0]），如果是最终状态，就表示搜索到一个结果，通过 PrintResult()函数遍历状态列表，输出当前结果状态转换的整个过程（倒水动作序列）。如果当前状态不是最终状态，就通过一个两重循环遍历 6 种可能的倒水动作。</p>
<figure class="highlight cpp"><table><tr><td class=gutter><pre><div class=line>1</div><div class=line>2</div><div class=line>3</div><div class=line>4</div><div class=line>5</div><div class=line>6</div><div class=line>7</div><div class=line>8</div><div class=line>9</div><div class=line>10</div><div class=line>11</div><div class=line>12</div><div class=line>13</div><div class=line>14</div></pre></td><td class=code><pre><div class=line><span class=keyword>void</span> SearchState(<span class=built_in>deque</span>& states) {</div><div class=line>	BucketState current = states.back(); <span class=comment>/* 每次都从当前状态开始 */</span></div><div class=line>	<span class=keyword>if</span>(current.IsFinalState()) {</div><div class=line>		PrintResult(states);</div><div class=line>		<span class=keyword>return</span>;</div><div class=line>	}</div><div class=line></div><div class=line>	<span class=comment>/* 使用两重循环排列组合 6 种倒水状态 */</span></div><div class=line>	<span class=keyword>for</span>(<span class=keyword>int</span> j = <span class=number>0</span>; j &lt; buckets_count; ++j) {</div><div class=line>		<span class=keyword>for</span>(<span class=keyword>int</span> i = <span class=number>0</span>; i &lt; buckets_count; ++i) {</div><div class=line>			SearchStateOnAction(states, current, i, j);</div><div class=line>		}</div><div class=line>	}</div><div class=line>}</div></pre></td></tr></table></figure>
<p>SearchStateOnAction()函数对每种可能的倒水动作检查是否是合法，如果是合法动作就生成一个新的状态，如果这个状态是状态列表中不存在的新状态，则将之加入到状态列表，然后递归地调用 SearchState()函数继续对新状态进行深度优先搜索。</p>
<p>SearchStateOnAction()函数的实现如下：</p>
<figure class="highlight cpp"><table><tr><td class=gutter><pre><div class=line>1</div><div class=line>2</div><div class=line>3</div><div class=line>4</div><div class=line>5</div><div class=line>6</div><div class=line>7</div><div class=line>8</div><div class=line>9</div><div class=line>10</div><div class=line>11</div><div class=line>12</div></pre></td><td class=code><pre><div class=line><span class=keyword>void</span> SearchStateOnAction(<span class=built_in>deque</span>& states, BucketState& current, <span class=keyword>int</span> from, <span class=keyword>int</span> to) {</div><div class=line>	<span class=keyword>if</span>(IsCurrentActionValid(current, from, to)) {</div><div class=line>		BucketState next;</div><div class=line>		<span class=comment>/* 从 from 到 to 倒水，如果成功，返回倒水后的状态 */</span></div><div class=line>		<span class=keyword>bool</span> bDump = current.DumpWater(from, to, next);</div><div class=line>		<span class=keyword>if</span>(bDump && !IsProcessedState(states, next)) {</div><div class=line>			states.push_back(next);</div><div class=line>			SearchState(states);</div><div class=line>			states.pop_back();</div><div class=line>		}</div><div class=line>	}</div><div class=line>}</div></pre></td></tr></table></figure>
<p>SearchStateOnAction()函数调用了一个很有意思的函数：DumpWater()。DumpWater()函数的主要作用是模拟一次倒水动作，确定能够从 from 桶中倒多少水到 to 桶，从而得到一个完整的动作三元组并根据这个动作从 current 状态生成新的状态 next。从 from 桶向 to 桶倒水只能有两种情况，一种是 from 的水被倒空（to 桶可能满，也可能不满），另一种是 to 桶被装满（from 桶可能还剩一些水，也可能被倒空），这两个约束在 DumpWater()函数中得到了体现：</p>
<figure class="highlight cpp"><table><tr><td class=gutter><pre><div class=line>1</div><div class=line>2</div><div class=line>3</div><div class=line>4</div><div class=line>5</div><div class=line>6</div><div class=line>7</div><div class=line>8</div><div class=line>9</div><div class=line>10</div><div class=line>11</div><div class=line>12</div><div class=line>13</div><div class=line>14</div><div class=line>15</div><div class=line>16</div><div class=line>17</div><div class=line>18</div></pre></td><td class=code><pre><div class=line><span class=keyword>bool</span> BucketState::DumpWater(<span class=keyword>int</span> from, <span class=keyword>int</span> to, BucketState& next) {</div><div class=line>	<span class=keyword>int</span> bucket_water[buckets_count] = {<span class=number>0</span> };</div><div class=line>	GetBuckets(bucket_water);</div><div class=line>	<span class=keyword>int</span> dump_water = bucket_capicity[to] - bucket_water[to];</div><div class=line>	<span class=keyword>if</span>(bucket_water[from] &gt;= dump_water) {</div><div class=line>		bucket_water[to] += dump_water;</div><div class=line>		bucket_water[from] -= dump_water;</div><div class=line>	} <span class=keyword>else</span> {</div><div class=line>		bucket_water[to] += bucket_water[from];</div><div class=line>		dump_water = bucket_water[from];</div><div class=line>		bucket_water[from] = <span class=number>0</span>;</div><div class=line>	}</div><div class=line>	<span class=keyword>if</span>(dump_water &gt; <span class=number>0</span>) {<span class=comment>/* 是一个有效的倒水动作 */</span></div><div class=line>		next.SetBuckets(bucket_water);</div><div class=line>		next.SetAction(dump_water, from, to);</div><div class=line>	}</div><div class=line>	<span class=keyword>return</span> (dump_water &gt; <span class=number>0</span>);</div><div class=line>}</div></pre></td></tr></table></figure>
<p><em>Find Result 1:</em></p>
<p>Dump 8 water from 0 to 1, buckets water states is : 8 0 0<br>Dump 5 water from 1 to 2, buckets water states is : 3 5 0<br>Dump 3 water from 1 to 3, buckets water states is : 0 5 3<br>Dump 5 water from 2 to 1, buckets water states is : 5 0 3<br>Dump 3 water from 3 to 2, buckets water states is : 5 3 0<br>Dump 3 water from 1 to 3, buckets water states is : 2 3 3<br>Dump 2 water from 3 to 2, buckets water states is : 2 5 1<br>Dump 5 water from 2 to 1, buckets water states is : 7 0 1<br>Dump 1 water from 3 to 2, buckets water states is : 7 1 0<br>Dump 3 water from 1 to 3, buckets water states is : 4 1 3<br>Dump 3 water from 3 to 2, buckets water states is : 4 4 0</p>
<p><em>Find Result 2:</em></p>
<p>Dump 8 water from 0 to 1, buckets water states is : 8 0 0<br>Dump 5 water from 1 to 2, buckets water states is : 3 5 0<br>Dump 3 water from 2 to 3, buckets water states is : 3 2 3<br>Dump 2 water from 2 to 1, buckets water states is : 5 0 3<br>Dump 3 water from 3 to 2, buckets water states is : 5 3 0<br>Dump 3 water from 1 to 3, buckets water states is : 2 3 3<br>Dump 2 water from 3 to 2, buckets water states is : 2 5 1<br>Dump 5 water from 2 to 1, buckets water states is : 7 0 1<br>Dump 1 water from 3 to 2, buckets water states is : 7 1 0<br>Dump 3 water from 1 to 3, buckets water states is : 4 1 3<br>Dump 3 water from 3 to 2, buckets water states is : 4 4 0</p>
<p><em>Find Result 3:</em></p>
<p>Dump 8 water from 0 to 1, buckets water states is : 8 0 0<br>Dump 5 water from 1 to 2, buckets water states is : 3 5 0<br>Dump 3 water from 2 to 3, buckets water states is : 3 2 3<br>Dump 3 water from 3 to 1, buckets water states is : 6 2 0<br>Dump 2 water from 2 to 3, buckets water states is : 6 0 2<br>Dump 5 water from 1 to 2, buckets water states is : 1 5 2<br>Dump 1 water from 1 to 3, buckets water states is : 0 5 3<br>Dump 5 water from 2 to 1, buckets water states is : 5 0 3<br>Dump 3 water from 3 to 2, buckets water states is : 5 3 0<br>Dump 3 water from 1 to 3, buckets water states is : 2 3 3<br>Dump 2 water from 3 to 2, buckets water states is : 2 5 1<br>Dump 5 water from 2 to 1, buckets water states is : 7 0 1<br>Dump 1 water from 3 to 2, buckets water states is : 7 1 0<br>Dump 3 water from 1 to 3, buckets water states is : 4 1 3<br>Dump 3 water from 3 to 2, buckets water states is : 4 4 0</p>
<p><em>Find Result 4:</em></p>
<p>Dump 8 water from 0 to 1, buckets water states is : 8 0 0<br>Dump 5 water from 1 to 2, buckets water states is : 3 5 0<br>Dump 3 water from 2 to 3, buckets water states is : 3 2 3<br>Dump 3 water from 3 to 1, buckets water states is : 6 2 0<br>Dump 2 water from 2 to 3, buckets water states is : 6 0 2<br>Dump 5 water from 1 to 2, buckets water states is : 1 5 2<br>Dump 1 water from 2 to 3, buckets water states is : 1 4 3<br>Dump 4 water from 2 to 1, buckets water states is : 5 0 3<br>Dump 3 water from 3 to 2, buckets water states is : 5 3 0<br>Dump 3 water from 1 to 3, buckets water states is : 2 3 3<br>Dump 2 water from 3 to 2, buckets water states is : 2 5 1<br>Dump 5 water from 2 to 1, buckets water states is : 7 0 1<br>Dump 1 water from 3 to 2, buckets water states is : 7 1 0<br>Dump 3 water from 1 to 3, buckets water states is : 4 1 3<br>Dump 3 water from 3 to 2, buckets water states is : 4 4 0</p>
<p><em>Find Result 5:</em></p>
<p>Dump 8 water from 0 to 1, buckets water states is : 8 0 0<br>Dump 5 water from 1 to 2, buckets water states is : 3 5 0<br>Dump 3 water from 2 to 3, buckets water states is : 3 2 3<br>Dump 3 water from 3 to 1, buckets water states is : 6 2 0<br>Dump 2 water from 2 to 3, buckets water states is : 6 0 2<br>Dump 5 water from 1 to 2, buckets water states is : 1 5 2<br>Dump 1 water from 2 to 3, buckets water states is : 1 4 3<br>Dump 3 water from 3 to 1, buckets water states is : 4 4 0</p>
<p><em>Find Result 6:</em></p>
<p>Dump 8 water from 0 to 1, buckets water states is : 8 0 0<br>Dump 5 water from 1 to 2, buckets water states is : 3 5 0<br>Dump 3 water from 2 to 3, buckets water states is : 3 2 3<br>Dump 3 water from 3 to 1, buckets water states is : 6 2 0<br>Dump 2 water from 2 to 3, buckets water states is : 6 0 2<br>Dump 5 water from 1 to 2, buckets water states is : 1 5 2<br>Dump 1 water from 2 to 3, buckets water states is : 1 4 3<br>Dump 1 water from 1 to 2, buckets water states is : 0 5 3<br>Dump 5 water from 2 to 1, buckets water states is : 5 0 3<br>Dump 3 water from 3 to 2, buckets water states is : 5 3 0<br>Dump 3 water from 1 to 3, buckets water states is : 2 3 3<br>Dump 2 water from 3 to 2, buckets water states is : 2 5 1<br>Dump 5 water from 2 to 1, buckets water states is : 7 0 1<br>Dump 1 water from 3 to 2, buckets water states is : 7 1 0<br>Dump 3 water from 1 to 3, buckets water states is : 4 1 3<br>Dump 3 water from 3 to 2, buckets water states is : 4 4 0</p>
<p><em>Find Result 7:</em></p>
<p>Dump 8 water from 0 to 1, buckets water states is : 8 0 0<br>Dump 5 water from 1 to 2, buckets water states is : 3 5 0<br>Dump 3 water from 2 to 3, buckets water states is : 3 2 3<br>Dump 3 water from 3 to 1, buckets water states is : 6 2 0<br>Dump 2 water from 2 to 3, buckets water states is : 6 0 2<br>Dump 1 water from 1 to 3, buckets water states is : 5 0 3<br>Dump 3 water from 3 to 2, buckets water states is : 5 3 0<br>Dump 3 water from 1 to 3, buckets water states is : 2 3 3<br>Dump 2 water from 3 to 2, buckets water states is : 2 5 1<br>Dump 5 water from 2 to 1, buckets water states is : 7 0 1<br>Dump 1 water from 3 to 2, buckets water states is : 7 1 0<br>Dump 3 water from 1 to 3, buckets water states is : 4 1 3<br>Dump 3 water from 3 to 2, buckets water states is : 4 4 0</p>
<p><em>Find Result 8:</em></p>
<p>Dump 8 water from 0 to 1, buckets water states is : 8 0 0<br>Dump 5 water from 1 to 2, buckets water states is : 3 5 0<br>Dump 3 water from 2 to 3, buckets water states is : 3 2 3<br>Dump 3 water from 1 to 2, buckets water states is : 0 5 3<br>Dump 5 water from 2 to 1, buckets water states is : 5 0 3<br>Dump 3 water from 3 to 2, buckets water states is : 5 3 0<br>Dump 3 water from 1 to 3, buckets water states is : 2 3 3<br>Dump 2 water from 3 to 2, buckets water states is : 2 5 1<br>Dump 5 water from 2 to 1, buckets water states is : 7 0 1<br>Dump 1 water from 3 to 2, buckets water states is : 7 1 0<br>Dump 3 water from 1 to 3, buckets water states is : 4 1 3<br>Dump 3 water from 3 to 2, buckets water states is : 4 4 0</p>
<p><em>Find Result 9:</em></p>
<p>Dump 8 water from 0 to 1, buckets water states is : 8 0 0<br>Dump 3 water from 1 to 3, buckets water states is : 5 0 3<br>Dump 5 water from 1 to 2, buckets water states is : 0 5 3<br>Dump 3 water from 3 to 1, buckets water states is : 3 5 0<br>Dump 3 water from 2 to 3, buckets water states is : 3 2 3<br>Dump 3 water from 3 to 1, buckets water states is : 6 2 0<br>Dump 2 water from 2 to 3, buckets water states is : 6 0 2<br>Dump 5 water from 1 to 2, buckets water states is : 1 5 2<br>Dump 1 water from 2 to 3, buckets water states is : 1 4 3<br>Dump 3 water from 3 to 1, buckets water states is : 4 4 0</p>
<p><em>Find Result 10:</em></p>
<p>Dump 8 water from 0 to 1, buckets water states is : 8 0 0<br>Dump 3 water from 1 to 3, buckets water states is : 5 0 3<br>Dump 3 water from 3 to 2, buckets water states is : 5 3 0<br>Dump 2 water from 1 to 2, buckets water states is : 3 5 0<br>Dump 3 water from 2 to 3, buckets water states is : 3 2 3<br>Dump 3 water from 3 to 1, buckets water states is : 6 2 0<br>Dump 2 water from 2 to 3, buckets water states is : 6 0 2<br>Dump 5 water from 1 to 2, buckets water states is : 1 5 2<br>Dump 1 water from 2 to 3, buckets water states is : 1 4 3<br>Dump 3 water from 3 to 1, buckets water states is : 4 4 0</p>
<p><em>Find Result 11:</em></p>
<p>Dump 8 water from 0 to 1, buckets water states is : 8 0 0<br>Dump 3 water from 1 to 3, buckets water states is : 5 0 3<br>Dump 3 water from 3 to 2, buckets water states is : 5 3 0<br>Dump 3 water from 1 to 3, buckets water states is : 2 3 3<br>Dump 2 water from 1 to 2, buckets water states is : 0 5 3<br>Dump 3 water from 3 to 1, buckets water states is : 3 5 0<br>Dump 3 water from 2 to 3, buckets water states is : 3 2 3<br>Dump 3 water from 3 to 1, buckets water states is : 6 2 0<br>Dump 2 water from 2 to 3, buckets water states is : 6 0 2<br>Dump 5 water from 1 to 2, buckets water states is : 1 5 2<br>Dump 1 water from 2 to 3, buckets water states is : 1 4 3<br>Dump 3 water from 3 to 1, buckets water states is : 4 4 0</p>
<p><em>Find Result 12:</em></p>
<p>Dump 8 water from 0 to 1, buckets water states is : 8 0 0<br>Dump 3 water from 1 to 3, buckets water states is : 5 0 3<br>Dump 3 water from 3 to 2, buckets water states is : 5 3 0<br>Dump 3 water from 1 to 3, buckets water states is : 2 3 3<br>Dump 2 water from 3 to 2, buckets water states is : 2 5 1<br>Dump 5 water from 2 to 1, buckets water states is : 7 0 1<br>Dump 1 water from 3 to 2, buckets water states is : 7 1 0<br>Dump 4 water from 1 to 2, buckets water states is : 3 5 0<br>Dump 3 water from 2 to 3, buckets water states is : 3 2 3<br>Dump 3 water from 3 to 1, buckets water states is : 6 2 0<br>Dump 2 water from 2 to 3, buckets water states is : 6 0 2<br>Dump 5 water from 1 to 2, buckets water states is : 1 5 2<br>Dump 1 water from 2 to 3, buckets water states is : 1 4 3<br>Dump 3 water from 3 to 1, buckets water states is : 4 4 0</p>
<p><em>Find Result 13:</em></p>
<p>Dump 8 water from 0 to 1, buckets water states is : 8 0 0<br>Dump 3 water from 1 to 3, buckets water states is : 5 0 3<br>Dump 3 water from 3 to 2, buckets water states is : 5 3 0<br>Dump 3 water from 1 to 3, buckets water states is : 2 3 3<br>Dump 2 water from 3 to 2, buckets water states is : 2 5 1<br>Dump 5 water from 2 to 1, buckets water states is : 7 0 1<br>Dump 1 water from 3 to 2, buckets water states is : 7 1 0<br>Dump 3 water from 1 to 3, buckets water states is : 4 1 3<br>Dump 4 water from 1 to 2, buckets water states is : 0 5 3<br>Dump 3 water from 3 to 1, buckets water states is : 3 5 0<br>Dump 3 water from 2 to 3, buckets water states is : 3 2 3<br>Dump 3 water from 3 to 1, buckets water states is : 6 2 0<br>Dump 2 water from 2 to 3, buckets water states is : 6 0 2<br>Dump 5 water from 1 to 2, buckets water states is : 1 5 2<br>Dump 1 water from 2 to 3, buckets water states is : 1 4 3<br>Dump 3 water from 3 to 1, buckets water states is : 4 4 0</p>
<p><em>Find Result 14:</em></p>
<p>Dump 8 water from 0 to 1, buckets water states is : 8 0 0<br>Dump 3 water from 1 to 3, buckets water states is : 5 0 3<br>Dump 3 water from 3 to 2, buckets water states is : 5 3 0<br>Dump 3 water from 1 to 3, buckets water states is : 2 3 3<br>Dump 2 water from 3 to 2, buckets water states is : 2 5 1<br>Dump 5 water from 2 to 1, buckets water states is : 7 0 1<br>Dump 1 water from 3 to 2, buckets water states is : 7 1 0<br>Dump 3 water from 1 to 3, buckets water states is : 4 1 3<br>Dump 3 water from 3 to 2, buckets water states is : 4 4 0</p>
<p><em>Find Result 15:</em></p>
<p>Dump 8 water from 0 to 1, buckets water states is : 8 0 0<br>Dump 3 water from 1 to 3, buckets water states is : 5 0 3<br>Dump 3 water from 3 to 2, buckets water states is : 5 3 0<br>Dump 3 water from 1 to 3, buckets water states is : 2 3 3<br>Dump 2 water from 3 to 2, buckets water states is : 2 5 1<br>Dump 1 water from 3 to 1, buckets water states is : 3 5 0<br>Dump 3 water from 2 to 3, buckets water states is : 3 2 3<br>Dump 3 water from 3 to 1, buckets water states is : 6 2 0<br>Dump 2 water from 2 to 3, buckets water states is : 6 0 2<br>Dump 5 water from 1 to 2, buckets water states is : 1 5 2<br>Dump 1 water from 2 to 3, buckets water states is : 1 4 3<br>Dump 3 water from 3 to 1, buckets water states is : 4 4 0</p>
<p><em>Find Result 16:</em></p>
<p>Dump 8 water from 0 to 1, buckets water states is : 8 0 0<br>Dump 3 water from 1 to 3, buckets water states is : 5 0 3<br>Dump 3 water from 3 to 2, buckets water states is : 5 3 0<br>Dump 3 water from 1 to 3, buckets water states is : 2 3 3<br>Dump 2 water from 3 to 2, buckets water states is : 2 5 1<br>Dump 2 water from 1 to 3, buckets water states is : 0 5 3<br>Dump 3 water from 3 to 1, buckets water states is : 3 5 0<br>Dump 3 water from 2 to 3, buckets water states is : 3 2 3<br>Dump 3 water from 3 to 1, buckets water states is : 6 2 0<br>Dump 2 water from 2 to 3, buckets water states is : 6 0 2<br>Dump 5 water from 1 to 2, buckets water states is : 1 5 2<br>Dump 1 water from 2 to 3, buckets water states is : 1 4 3<br>Dump 3 water from 3 to 1, buckets water states is : 4 4 0</p>
<h2 id=完整源代码>完整源代码</h2>
<figure class="highlight cpp"><table><tr><td class=gutter><pre><div class=line>1</div><div class=line>2</div><div class=line>3</div><div class=line>4</div><div class=line>5</div><div class=line>6</div><div class=line>7</div><div class=line>8</div><div class=line>9</div><div class=line>10</div><div class=line>11</div><div class=line>12</div><div class=line>13</div><div class=line>14</div><div class=line>15</div><div class=line>16</div><div class=line>17</div><div class=line>18</div><div class=line>19</div><div class=line>20</div><div class=line>21</div><div class=line>22</div><div class=line>23</div><div class=line>24</div><div class=line>25</div><div class=line>26</div><div class=line>27</div><div class=line>28</div><div class=line>29</div><div class=line>30</div><div class=line>31</div><div class=line>32</div><div class=line>33</div><div class=line>34</div><div class=line>35</div><div class=line>36</div><div class=line>37</div><div class=line>38</div><div class=line>39</div><div class=line>40</div><div class=line>41</div><div class=line>42</div><div class=line>43</div><div class=line>44</div><div class=line>45</div><div class=line>46</div><div class=line>47</div><div class=line>48</div><div class=line>49</div><div class=line>50</div><div class=line>51</div><div class=line>52</div><div class=line>53</div><div class=line>54</div><div class=line>55</div><div class=line>56</div><div class=line>57</div><div class=line>58</div><div class=line>59</div><div class=line>60</div><div class=line>61</div><div class=line>62</div><div class=line>63</div><div class=line>64</div><div class=line>65</div><div class=line>66</div><div class=line>67</div><div class=line>68</div><div class=line>69</div><div class=line>70</div><div class=line>71</div><div class=line>72</div><div class=line>73</div><div class=line>74</div><div class=line>75</div><div class=line>76</div><div class=line>77</div><div class=line>78</div><div class=line>79</div><div class=line>80</div><div class=line>81</div><div class=line>82</div><div class=line>83</div><div class=line>84</div><div class=line>85</div><div class=line>86</div><div class=line>87</div><div class=line>88</div><div class=line>89</div><div class=line>90</div><div class=line>91</div><div class=line>92</div><div class=line>93</div><div class=line>94</div><div class=line>95</div><div class=line>96</div><div class=line>97</div><div class=line>98</div><div class=line>99</div><div class=line>100</div><div class=line>101</div><div class=line>102</div><div class=line>103</div><div class=line>104</div><div class=line>105</div><div class=line>106</div><div class=line>107</div><div class=line>108</div><div class=line>109</div><div class=line>110</div><div class=line>111</div><div class=line>112</div><div class=line>113</div><div class=line>114</div><div class=line>115</div><div class=line>116</div><div class=line>117</div><div class=line>118</div><div class=line>119</div><div class=line>120</div><div class=line>121</div><div class=line>122</div><div class=line>123</div><div class=line>124</div><div class=line>125</div><div class=line>126</div><div class=line>127</div><div class=line>128</div><div class=line>129</div><div class=line>130</div><div class=line>131</div><div class=line>132</div><div class=line>133</div><div class=line>134</div><div class=line>135</div><div class=line>136</div><div class=line>137</div><div class=line>138</div><div class=line>139</div><div class=line>140</div><div class=line>141</div><div class=line>142</div><div class=line>143</div><div class=line>144</div><div class=line>145</div><div class=line>146</div><div class=line>147</div><div class=line>148</div><div class=line>149</div><div class=line>150</div><div class=line>151</div><div class=line>152</div><div class=line>153</div><div class=line>154</div><div class=line>155</div><div class=line>156</div><div class=line>157</div><div class=line>158</div><div class=line>159</div><div class=line>160</div><div class=line>161</div><div class=line>162</div><div class=line>163</div><div class=line>164</div><div class=line>165</div><div class=line>166</div><div class=line>167</div><div class=line>168</div><div class=line>169</div><div class=line>170</div><div class=line>171</div><div class=line>172</div><div class=line>173</div><div class=line>174</div><div class=line>175</div><div class=line>176</div><div class=line>177</div><div class=line>178</div><div class=line>179</div><div class=line>180</div><div class=line>181</div><div class=line>182</div><div class=line>183</div><div class=line>184</div><div class=line>185</div><div class=line>186</div><div class=line>187</div><div class=line>188</div><div class=line>189</div><div class=line>190</div><div class=line>191</div><div class=line>192</div><div class=line>193</div><div class=line>194</div><div class=line>195</div><div class=line>196</div><div class=line>197</div><div class=line>198</div><div class=line>199</div><div class=line>200</div><div class=line>201</div><div class=line>202</div><div class=line>203</div><div class=line>204</div><div class=line>205</div><div class=line>206</div><div class=line>207</div><div class=line>208</div><div class=line>209</div><div class=line>210</div><div class=line>211</div><div class=line>212</div><div class=line>213</div><div class=line>214</div><div class=line>215</div><div class=line>216</div><div class=line>217</div><div class=line>218</div><div class=line>219</div><div class=line>220</div><div class=line>221</div><div class=line>222</div><div class=line>223</div><div class=line>224</div><div class=line>225</div><div class=line>226</div><div class=line>227</div><div class=line>228</div><div class=line>229</div><div class=line>230</div><div class=line>231</div><div class=line>232</div><div class=line>233</div><div class=line>234</div><div class=line>235</div><div class=line>236</div></pre></td><td class=code><pre><div class=line><span class=preprocessor>#<span class=keyword>include</span> &lt;deque&gt;</span></div><div class=line><span class=preprocessor>#<span class=keyword>include</span> &lt;vector&gt;</span></div><div class=line><span class=preprocessor>#<span class=keyword>include</span> &lt;algorithm&gt;</span></div><div class=line><span class=preprocessor>#<span class=keyword>include</span> &lt;iostream&gt;</span></div><div class=line><span class=preprocessor>#<span class=keyword>include</span> &lt;functional&gt;</span></div><div class=line><span class=preprocessor>#<span class=keyword>include</span> &lt;cassert&gt;</span></div><div class=line></div><div class=line><span class=keyword>const</span> <span class=keyword>int</span> buckets_count = <span class=number>3</span>;</div><div class=line></div><div class=line><span class=keyword>struct</span> Action</div><div class=line>{</div><div class=line>	<span class=keyword>int</span> from;</div><div class=line>	<span class=keyword>int</span> to;</div><div class=line>	<span class=keyword>int</span> water;</div><div class=line>};</div><div class=line></div><div class=line><span class=keyword>struct</span> BucketState</div><div class=line>{</div><div class=line>	BucketState();</div><div class=line>	BucketState(<span class=keyword>const</span> <span class=keyword>int</span> *buckets);</div><div class=line>	BucketState(<span class=keyword>const</span> BucketState& state);</div><div class=line>	BucketState& <span class=keyword>operator</span>=(<span class=keyword>const</span> BucketState& state);</div><div class=line>	<span class=keyword>bool</span> IsSameState(<span class=keyword>const</span> BucketState& state) <span class=keyword>const</span>;</div><div class=line>	<span class=keyword>void</span> SetAction(<span class=keyword>int</span> w, <span class=keyword>int</span> f, <span class=keyword>int</span> t);</div><div class=line>	<span class=keyword>void</span> SetBuckets(<span class=keyword>const</span> <span class=keyword>int</span> *buckets);</div><div class=line>	<span class=keyword>void</span> GetBuckets(<span class=keyword>int</span> *buckets) <span class=keyword>const</span>;</div><div class=line>	<span class=keyword>bool</span> IsBucketEmpty(<span class=keyword>int</span> bucket);</div><div class=line>	<span class=keyword>bool</span> IsBucketFull(<span class=keyword>int</span> bucket);</div><div class=line>	<span class=keyword>void</span> PrintStates();</div><div class=line>	<span class=keyword>bool</span> IsFinalState();</div><div class=line>	<span class=keyword>bool</span> DumpWater(<span class=keyword>int</span> from, <span class=keyword>int</span> to, BucketState& next);</div><div class=line>	<span class=keyword>int</span> bucket_s[buckets_count];</div><div class=line>	Action curAction;</div><div class=line>};</div><div class=line></div><div class=line><span class=keyword>int</span> bucket_capicity[buckets_count] = {<span class=number>8</span>, <span class=number>5</span>, <span class=number>3</span>};</div><div class=line><span class=keyword>int</span> bucket_init_state[buckets_count]  = {<span class=number>8</span>, <span class=number>0</span>, <span class=number>0</span>};</div><div class=line><span class=keyword>int</span> bucket_final_state[buckets_count] = {<span class=number>4</span>, <span class=number>4</span>, <span class=number>0</span>};</div><div class=line></div><div class=line><span class=keyword>void</span> CopyStateArray(<span class=keyword>const</span> <span class=keyword>int</span> *from, <span class=keyword>int</span> *to, <span class=keyword>int</span> count)</div><div class=line>{</div><div class=line>	<span class=keyword>for</span>(<span class=keyword>int</span> i = <span class=number>0</span>; i &lt; count; ++i)</div><div class=line>	{</div><div class=line>		to[i] = from[i];</div><div class=line>	}</div><div class=line>}</div><div class=line></div><div class=line>BucketState::BucketState()</div><div class=line>{</div><div class=line>	SetBuckets(bucket_init_state);</div><div class=line>	SetAction(<span class=number>8</span>, -<span class=number>1</span>, <span class=number>0</span>);</div><div class=line>}</div><div class=line></div><div class=line>BucketState::BucketState(<span class=keyword>const</span> <span class=keyword>int</span> *buckets)</div><div class=line>{</div><div class=line>	SetBuckets(buckets);</div><div class=line>	SetAction(<span class=number>8</span>, -<span class=number>1</span>, <span class=number>0</span>);</div><div class=line>}</div><div class=line></div><div class=line>BucketState::BucketState(<span class=keyword>const</span> BucketState& state)</div><div class=line>{</div><div class=line>	SetBuckets((<span class=keyword>const</span> <span class=keyword>int</span> *)state.bucket_s);</div><div class=line>	SetAction(state.curAction.water, state.curAction.from, state.curAction.to);</div><div class=line>}</div><div class=line></div><div class=line>BucketState& BucketState::<span class=keyword>operator</span>=(<span class=keyword>const</span> BucketState& state)</div><div class=line>{</div><div class=line>	SetBuckets((<span class=keyword>const</span> <span class=keyword>int</span> *)state.bucket_s);</div><div class=line>	SetAction(state.curAction.water, state.curAction.from, state.curAction.to);</div><div class=line>	<span class=keyword>return</span> *<span class=keyword>this</span>;</div><div class=line>}</div><div class=line></div><div class=line><span class=keyword>bool</span> BucketState::IsSameState(<span class=keyword>const</span> BucketState& state) <span class=keyword>const</span></div><div class=line>{</div><div class=line>	<span class=keyword>for</span>(<span class=keyword>int</span> i = <span class=number>0</span>; i &lt; buckets_count; ++i)</div><div class=line>	{</div><div class=line>		<span class=keyword>if</span>(bucket_s[i] != state.bucket_s[i])</div><div class=line>			<span class=keyword>return</span> <span class=keyword>false</span>;</div><div class=line>	}</div><div class=line></div><div class=line>	<span class=keyword>return</span> <span class=keyword>true</span>;</div><div class=line>}</div><div class=line></div><div class=line><span class=keyword>void</span> BucketState::SetAction(<span class=keyword>int</span> w, <span class=keyword>int</span> f, <span class=keyword>int</span> t)</div><div class=line>{</div><div class=line>	curAction.water = w;</div><div class=line>	curAction.from  = f;</div><div class=line>	curAction.to	= t;</div><div class=line>}</div><div class=line></div><div class=line><span class=keyword>void</span> BucketState::SetBuckets(<span class=keyword>const</span> <span class=keyword>int</span> *buckets)</div><div class=line>{</div><div class=line>	CopyStateArray(buckets, (<span class=keyword>int</span> *)bucket_s, buckets_count);</div><div class=line>}</div><div class=line></div><div class=line><span class=keyword>void</span> BucketState::GetBuckets(<span class=keyword>int</span> *buckets) <span class=keyword>const</span></div><div class=line>{</div><div class=line>	CopyStateArray((<span class=keyword>const</span> <span class=keyword>int</span> *)bucket_s, buckets, buckets_count);</div><div class=line>}</div><div class=line></div><div class=line><span class=keyword>bool</span> BucketState::IsBucketEmpty(<span class=keyword>int</span> bucket)</div><div class=line>{</div><div class=line>	assert((bucket &gt;= <span class=number>0</span>) && (bucket &lt; buckets_count));</div><div class=line></div><div class=line>	<span class=keyword>return</span> (bucket_s[bucket] == <span class=number>0</span>);</div><div class=line>}</div><div class=line></div><div class=line><span class=keyword>bool</span> BucketState::IsBucketFull(<span class=keyword>int</span> bucket)</div><div class=line>{</div><div class=line>	assert((bucket &gt;= <span class=number>0</span>) && (bucket &lt; buckets_count));</div><div class=line></div><div class=line>	<span class=keyword>return</span> (bucket_s[bucket] &gt;= bucket_capicity[bucket]);</div><div class=line>}</div><div class=line></div><div class=line><span class=keyword>void</span> BucketState::PrintStates()</div><div class=line>{</div><div class=line>	<span class=built_in>cout</span> &lt;&lt; <span class=string>"Dump"</span> &lt;&lt; curAction.water &lt;&lt; <span class=string>"water from"</span></div><div class=line>		 &lt;&lt; curAction.from + <span class=number>1</span> &lt;&lt; <span class=string>"to"</span> &lt;&lt; curAction.to + <span class=number>1</span> &lt;&lt; <span class=string>","</span>;</div><div class=line>	<span class=built_in>cout</span> &lt;&lt; <span class=string>"buckets water states is :"</span>;</div><div class=line></div><div class=line>	<span class=keyword>for</span>(<span class=keyword>int</span> i = <span class=number>0</span>; i &lt; buckets_count; ++i)</div><div class=line>	{</div><div class=line>		<span class=built_in>cout</span> &lt;&lt; bucket_s[i] &lt;&lt; <span class=string>""</span>;</div><div class=line>	}</div><div class=line>	<span class=built_in>cout</span> &lt;&lt; endl;</div><div class=line>}</div><div class=line></div><div class=line><span class=keyword>bool</span> BucketState::IsFinalState()</div><div class=line>{</div><div class=line>	<span class=keyword>return</span> IsSameState(BucketState(bucket_final_state));</div><div class=line>}</div><div class=line></div><div class=line><span class=comment>/* 从 from 到 to 倒水，返回实际倒水体积 */</span></div><div class=line><span class=keyword>bool</span> BucketState::DumpWater(<span class=keyword>int</span> from, <span class=keyword>int</span> to, BucketState& next)</div><div class=line>{</div><div class=line>	<span class=keyword>int</span> bucket_water[buckets_count] = {<span class=number>0</span> };</div><div class=line></div><div class=line>	GetBuckets(bucket_water);</div><div class=line>	<span class=keyword>int</span> dump_water = bucket_capicity[to] - bucket_water[to];</div><div class=line>	<span class=keyword>if</span>(bucket_water[from] &gt;= dump_water)</div><div class=line>	{</div><div class=line>		bucket_water[to] += dump_water;</div><div class=line>		bucket_water[from] -= dump_water;</div><div class=line>	}</div><div class=line>	<span class=keyword>else</span></div><div class=line>	{</div><div class=line>		bucket_water[to] += bucket_water[from];</div><div class=line>		dump_water = bucket_water[from];</div><div class=line>		bucket_water[from] = <span class=number>0</span>;</div><div class=line>	}</div><div class=line>	<span class=keyword>if</span>(dump_water &gt; <span class=number>0</span>) <span class=comment>/* 是一个有效的倒水动作 */</span></div><div class=line>	{</div><div class=line>		next.SetBuckets(bucket_water);</div><div class=line>		next.SetAction(dump_water, from, to);</div><div class=line>	}</div><div class=line>	<span class=keyword>return</span> (dump_water &gt; <span class=number>0</span>);</div><div class=line>}</div><div class=line></div><div class=line><span class=keyword>bool</span> IsSameBucketState(BucketState state1, BucketState state2)</div><div class=line>{</div><div class=line>	<span class=keyword>return</span> state1.IsSameState(state2);</div><div class=line>}</div><div class=line></div><div class=line><span class=keyword>bool</span> IsProcessedState(<span class=stl_container><span class=built_in>deque</span>&lt;BucketState&gt;</span>& states, <span class=keyword>const</span> BucketState& newState)</div><div class=line>{</div><div class=line>	<span class=stl_container><span class=built_in>deque</span>&lt;BucketState&gt;</span>::iterator it = states.end();</div><div class=line>	it = find_if(states.begin(), states.end(),</div><div class=line>				  bind2nd(ptr_fun(IsSameBucketState), newState) );</div><div class=line>	<span class=keyword>return</span> (it != states.end());</div><div class=line>}</div><div class=line></div><div class=line><span class=keyword>void</span> PrintResult(<span class=stl_container><span class=built_in>deque</span>&lt;BucketState&gt;</span>& states)</div><div class=line>{</div><div class=line>	<span class=built_in>cout</span> &lt;&lt; <span class=string>"Find Result : "</span> &lt;&lt; endl;</div><div class=line>	for_each(states.begin(), states.end(),</div><div class=line>			 mem_fun_ref(&BucketState::PrintStates));</div><div class=line>	<span class=built_in>cout</span> &lt;&lt; endl &lt;&lt; endl;</div><div class=line>}</div><div class=line></div><div class=line><span class=keyword>bool</span> IsCurrentActionValid(BucketState& current, <span class=keyword>int</span> from, <span class=keyword>int</span> to)</div><div class=line>{</div><div class=line>	<span class=comment>/* 不是同一个桶，且 from 桶中有水，且 to 桶中不满 */</span></div><div class=line>	<span class=keyword>if</span>((from != to)</div><div class=line>		&& !current.IsBucketEmpty(from)</div><div class=line>		&& !current.IsBucketFull(to) )</div><div class=line>	{</div><div class=line>		<span class=keyword>return</span> <span class=keyword>true</span>;</div><div class=line>	}</div><div class=line>	<span class=keyword>return</span> <span class=keyword>false</span>;</div><div class=line>}</div><div class=line></div><div class=line><span class=keyword>void</span> SearchState(<span class=stl_container><span class=built_in>deque</span>&lt;BucketState&gt;</span>& states);</div><div class=line></div><div class=line><span class=keyword>void</span> SearchStateOnAction(<span class=stl_container><span class=built_in>deque</span>&lt;BucketState&gt;</span>& states, BucketState& current, <span class=keyword>int</span> from, <span class=keyword>int</span> to)</div><div class=line>{</div><div class=line>	<span class=keyword>if</span>(IsCurrentActionValid(current, from, to))</div><div class=line>	{</div><div class=line>		BucketState next;</div><div class=line>		 <span class=comment>/* 从 from 到 to 倒水，如果成功，返回倒水后的状态 */</span></div><div class=line>		<span class=keyword>bool</span> bDump = current.DumpWater(from, to, next);</div><div class=line>		<span class=keyword>if</span>(bDump && !IsProcessedState(states, next))</div><div class=line>		{</div><div class=line>			states.push_back(next);</div><div class=line>			SearchState(states);</div><div class=line>			states.pop_back();</div><div class=line>		}</div><div class=line>	}</div><div class=line>}</div><div class=line></div><div class=line><span class=keyword>void</span> SearchState(<span class=stl_container><span class=built_in>deque</span>&lt;BucketState&gt;</span>& states)</div><div class=line>{</div><div class=line>	BucketState current = states.back(); <span class=comment>/* 每次都从当前状态开始 */</span></div><div class=line>	<span class=keyword>if</span>(current.IsFinalState())</div><div class=line>	{</div><div class=line>		PrintResult(states);</div><div class=line>		<span class=keyword>return</span>;</div><div class=line>	}</div><div class=line>	<span class=comment>/* 使用两重循环排列组合种倒水状态 */</span></div><div class=line>	<span class=keyword>for</span>(<span class=keyword>int</span> j = <span class=number>0</span>; j &lt; buckets_count; ++j)</div><div class=line>	{</div><div class=line>		<span class=keyword>for</span>(<span class=keyword>int</span> i = <span class=number>0</span>; i &lt; buckets_count; ++i)</div><div class=line>		{</div><div class=line>			SearchStateOnAction(states, current, i, j);</div><div class=line>		}</div><div class=line>	}</div><div class=line>}</div><div class=line></div><div class=line><span class=keyword>int</span> main(<span class=keyword>int</span> argc, <span class=keyword>char</span>* argv[])</div><div class=line>{</div><div class=line>	<span class=stl_container><span class=built_in>deque</span>&lt;BucketState&gt;</span> states;</div><div class=line>	BucketState init;</div><div class=line>	states.push_back(init);</div><div class=line>	SearchState(states);</div><div class=line>	assert(states.size() == <span class=number>1</span>); <span class=comment>/* 穷举结束后 states 应该还是只有一个初始状态 */</span></div><div class=line>	<span class=keyword>return</span> <span class=number>0</span>;</div><div class=line>}</div></pre></td></tr></table></figure>
<p>本文转载自: <a href=http://blog.csdn.net/orbit/article/details/6596521 target=_blank rel=external>http://blog.csdn.net/orbit/article/details/6596521</a></p>
<div class=ujian-hook></div>
</div>
<footer class=article-footer>
<div class=bdsharebuttonbox>
<a href=# class=bds_tsina data-cmd=tsina title=分享到新浪微博></a>
<a href=# class=bds_qzone data-cmd=qzone title=分享到QQ空间></a>
<a href=# class=bds_tqq data-cmd=tqq title=分享到腾讯微博></a>
<a href=# class=bds_weixin data-cmd=weixin title=分享到微信></a>
<a href=# class=bds_tieba data-cmd=tieba title=分享到百度贴吧></a>
<a href=# class=bds_renren data-cmd=renren title=分享到人人网></a>
<a href=# class=bds_tqf data-cmd=tqf title=分享到腾讯朋友></a>
<a href=# class=bds_douban data-cmd=douban title=分享到豆瓣网></a>
<a href=# class=bds_tsohu data-cmd=tsohu title=分享到搜狐微博></a>
<a href=# class=bds_t163 data-cmd=t163 title=分享到网易微博></a>
<a href=# class=bds_taobao data-cmd=taobao title=分享到我的淘宝></a>
<a href=# class=bds_fx data-cmd=fx title=分享到飞信></a>
<a href=# class=bds_hi data-cmd=hi title=分享到百度空间></a>
<a href=# class=bds_more data-cmd=more></a>
</div>
<ul class=article-tag-list><li class=article-tag-list-item><a class=article-tag-list-link href=../tag/c++>C++</a></li><li class=article-tag-list-item><a class=article-tag-list-link href=../tag/程序设计>程序设计</a></li><li class=article-tag-list-item><a class=article-tag-list-link href=../tag/算法>算法</a></li><li class=article-tag-list-item><a class=article-tag-list-link href=../tag/编程>编程</a></li><li class=article-tag-list-item><a class=article-tag-list-link href=../tag/计算机>计算机</a></li></ul>
</footer>
</div>
<nav id=article-nav>
<a href="/switch-performance/" id=article-nav-newer class=article-nav-link-wrap>
<strong class=article-nav-caption>Newer</strong>
<div class=article-nav-title>
交换机技术指标 各参数含义及对性能影响
</div>
</a>
<a href="/photoshop-cs6-looks-like-flash/" id=article-nav-older class=article-nav-link-wrap>
<strong class=article-nav-caption>Older</strong>
<div class=article-nav-title>新版Photoshop向Flash看齐?</div>
</a>
</nav>
</article>
<section id=comments>
<div class=ds-thread data-thread-key="algorithm-pour-three-buckets/" data-title="算法: 三只水桶等分水问题" data-url="http://cweili.gitcafe.com/algorithm-pour-three-buckets/"></div>
</section>
</section>
<aside id=sidebar class=col-sm-3>
<div class="widget-wrap hidden-xs">
<h3 class=widget-title>分类</h3>
<div class=widget>
<ul class=category-list><li class=category-list-item><a class=category-list-link href=../category/学习笔记>学习笔记</a><span class=category-list-count>40</span></li><li class=category-list-item><a class=category-list-link href=../category/小生活>小生活</a><span class=category-list-count>27</span></li><li class=category-list-item><a class=category-list-link href=../category/杂物>杂物</a><span class=category-list-count>9</span></li></ul>
</div>
</div>
<div class=widget-wrap>
<h3 class=widget-title>最新评论</h3>
<div class=widget>
<div class=ds-recent-comments data-num-items=10 data-show-avatars=1 data-show-time=1 data-show-title=0 data-show-admin=1 data-excerpt-length=20>
<div class=text-center><i class="fa fa-refresh fa-spin"></i></div>
</div>
</div>
</div>
<div class=widget-wrap>
<h3 class=widget-title>最新文章</h3>
<div class=widget>
<ul>
<li>
<a href="/xixishidi/">河塘飞鸟西溪湿地</a>
</li>
<li>
<a href="/xizihu/">水光潋滟西子湖畔</a>
</li>
<li>
<a href="/xitang/">柳絮纷飞烟雨西塘</a>
</li>
<li>
<a href="/wuzhen/">灯火阑珊水映乌镇</a>
</li>
<li>
<a href="/stu3-zoo/">Stu3 Zoo</a>
</li>
<li>
<a href="/jshint-options/">JSHint配置参数详解</a>
</li>
<li>
<a href="/css3-jquery-rocket-to-top/">CSS3动画与jQuery实现返回顶部小火箭</a>
</li>
<li>
<a href="/rebuild-blog-gitcafe/">再一次重建我的博客</a>
</li>
<li>
<a href="/java-poi-excel/">Java使用POI创建Excel图表</a>
</li>
<li>
<a href="/hibernate-connect-sqlite-paging-bug-repair/">Hibernate 连接 SQLite (hibernate-sqlite) 分页bug的修复</a>
</li>
<li>
<a href="/web-page-color-chart/">更全的网页颜色表</a>
</li>
<li>
<a href="/quarrying-rocky-4/">20120407春游采石矶(四)</a>
</li>
<li>
<a href="/quarrying-rocky-3/">20120407春游采石矶(三)</a>
</li>
<li>
<a href="/quarrying-rocky-2/">20120407春游采石矶(二)</a>
</li>
<li>
<a href="/quarrying-rocky/">20120407春游采石矶(一)</a>
</li>
<li>
<a href="/ahpu-spring/">安徽工程大学的春天</a>
</li>
<li>
<a href="/helps-students-assembled-computer/">帮同学组装帅气小机箱电脑一台</a>
</li>
<li>
<a href="/nanjing-trip-4/">20120310南京二日行(四)</a>
</li>
<li>
<a href="/nanjing-trip-3/">20120310南京二日行(三)</a>
</li>
<li>
<a href="/nanjing-trip-2/">20120310南京二日行(二)</a>
</li>
</ul>
</div>
</div>
<div class="widget-wrap hidden-xs">
<h3 class=widget-title>手机阅读</h3>
<div class=widget>
<div class=qrcode style="background-image:url(http://qr.liantu.com/api.php?bg=eeeeee&fg=000000&el=l&w=192&m=0&text=http://cweili.gitcafe.com/algorithm-pour-three-buckets/)"></div>
</div>
</div>
<div class="widget-wrap hidden-xs">
<h3 class=widget-title>标签云</h3>
<div class="widget tagcloud">
<a href=../tag/acm style=font-size:10px>ACM</a><a href=../tag/c++ style=font-size:15.71px>C++</a><a href=../tag/css style=font-size:10px>CSS</a><a href=../tag/fedora style=font-size:15.71px>Fedora</a><a href=../tag/gnome style=font-size:11.43px>Gnome</a><a href=../tag/hibernate style=font-size:10px>Hibernate</a><a href=../tag/jshint style=font-size:10px>JSHint</a><a href=../tag/java style=font-size:11.43px>Java</a><a href=../tag/javascript style=font-size:12.86px>JavaScript</a><a href=../tag/linux style=font-size:17.14px>Linux</a><a href=../tag/pdo style=font-size:10px>PDO</a><a href=../tag/php style=font-size:12.86px>PHP</a><a href=../tag/poi style=font-size:10px>POI</a><a href=../tag/photoshop style=font-size:14.29px>Photoshop</a><a href=../tag/sae style=font-size:10px>SAE</a><a href=../tag/sql style=font-size:14.29px>SQL</a><a href=../tag/sqlite style=font-size:11.43px>SQLite</a><a href=../tag/stl style=font-size:11.43px>STL</a><a href=../tag/stu3 style=font-size:10px>Stu3</a><a href=../tag/twitter style=font-size:10px>Twitter</a><a href=../tag/virtualbox style=font-size:10px>VirtualBox</a><a href=../tag/jquery style=font-size:10px>jQuery</a><a href=../tag/三国杀 style=font-size:15.71px>三国杀</a><a href=../tag/乌镇 style=font-size:10px>乌镇</a><a href=../tag/互联网 style=font-size:10px>互联网</a><a href=../tag/动漫 style=font-size:11.43px>动漫</a><a href=../tag/动画 style=font-size:10px>动画</a><a href=../tag/南京 style=font-size:14.29px>南京</a><a href=../tag/博客 style=font-size:14.29px>博客</a><a href=../tag/实验 style=font-size:15.71px>实验</a><a href=../tag/容器 style=font-size:11.43px>容器</a><a href=../tag/小说 style=font-size:10px>小说</a><a href=../tag/微博 style=font-size:11.43px>微博</a><a href=../tag/心情 style=font-size:14.29px>心情</a><a href=../tag/摄影 style=font-size:17.14px>摄影</a><a href=../tag/操作系统 style=font-size:14.29px>操作系统</a><a href=../tag/数据库 style=font-size:18.57px>数据库</a><a href=../tag/旅行 style=font-size:20px>旅行</a><a href=../tag/日记 style=font-size:17.14px>日记</a><a href=../tag/杭州 style=font-size:11.43px>杭州</a>
</div>
</div>
<div class="widget-wrap hidden-xs">
<h3 class=widget-title>归档</h3>
<div class=widget>
<ul class=archive-list><li class=archive-list-item><a class=archive-list-link href=../archive/2014/09>September 2014</a><span class=archive-list-count>4</span></li><li class=archive-list-item><a class=archive-list-link href=../archive/2014/08>August 2014</a><span class=archive-list-count>4</span></li><li class=archive-list-item><a class=archive-list-link href=../archive/2012/09>September 2012</a><span class=archive-list-count>1</span></li><li class=archive-list-item><a class=archive-list-link href=../archive/2012/05>May 2012</a><span class=archive-list-count>2</span></li><li class=archive-list-item><a class=archive-list-link href=../archive/2012/04>April 2012</a><span class=archive-list-count>5</span></li><li class=archive-list-item><a class=archive-list-link href=../archive/2012/03>March 2012</a><span class=archive-list-count>5</span></li><li class=archive-list-item><a class=archive-list-link href=../archive/2011/12>December 2011</a><span class=archive-list-count>4</span></li><li class=archive-list-item><a class=archive-list-link href=../archive/2011/11>November 2011</a><span class=archive-list-count>18</span></li><li class=archive-list-item><a class=archive-list-link href=../archive/2011/10>October 2011</a><span class=archive-list-count>32</span></li><li class=archive-list-item><a class=archive-list-link href=../archive/2011/05>May 2011</a><span class=archive-list-count>2</span></li></ul>
</div>
</div>
<div class="widget-wrap hidden-xs">
<h3 class=widget-title>友情链接</h3>
<div class=widget>
<ul>
<li>
<a href=http://cweili.gitcafe.com target=_blank>主页</a>
</li>
</ul>
</div>
</div>
</aside>
</div>
<footer id=footer>
<div class=footer-wrap>
<div class=outer>
<div class=inner>
<div id=social-network>
<a class=link href=https://github.com/Cweili target=_blank><i class="fa fa-fw fa-github"></i></a>
<a class=link href=http://weibo.com/cweili target=_blank><i class="fa fa-fw fa-weibo"></i></a>
</div>
<div id=footer-info>
&copy; 2014 <a href=http://cweili.gitcafe.com target=_blank>Cweili</a><br>
Powered by <a href="http://hexo.io/" target=_blank>Hexo</a>.
Theme by <a href=http://cweili.gitcafe.com target=_blank>Cweili</a>.
</div>
</div>
</div>
</div>
</footer>
</div>
</div>
<div id=rocket-to-top>
<div class=onhover></div>
<div class=anim></div>
</div>
<link rel=stylesheet href=//libs.baidu.com/fontawesome/4.0.3/css/font-awesome.min.css css type=text/css>
<script src=//libs.baidu.com/jquery/1.11.1/jquery.min.js type=text/javascript></script><link rel=stylesheet href=//cdn.staticfile.org/fancybox/2.1.5/jquery.fancybox.min.css type=text/css>
<script src=//cdn.staticfile.org/fancybox/2.1.5/jquery.fancybox.min.js type=text/javascript></script><script src=../js/script.js type=text/javascript></script><script type=text/javascript>var duoshuoQuery={short_name:"cweiligitcafe"};</script><script src=//static.duoshuo.com/embed.js type=text/javascript></script><script type=text/javascript>var ujian_config={num:10,showType:3};</script><script src="http://v1.ujian.cc/code/ujian.js?uid=1539214&_=.js" type=text/javascript></script><script type=text/javascript>window._bd_share_config={common:{bdSnsKey:{},bdPopTitle:"分享到",bdMini:2,bdPopupOffsetLeft:28,bdPopupOffsetTop:108,bdMiniList:["sqq","mshare","bdysc","kaixin001","ibaidu","baidu","ff","qy","meilishuo","mogujie","diandian","ty","youdao","sdo"],bdPic:"",bdStyle:1,bdSize:"24"},share:{},image:{viewList:["tsina","qzone","tqq","weixin","tieba","renren","tqf","douban","tsohu","t163","taobao","fx","hi"],viewText:" ",viewSize:"24"},selectShare:{bdContainerClass:"article",bdSelectMiniList:["tsina","qzone","tqq","weixin","tieba","renren","tqf","douban","tsohu","t163","taobao","fx","hi"]}},document.write('<script type="text/javascript" src="http://bdimg.share.baidu.com/static/api/js/share.js?cdnversion='+~(-new Date/36e5)+'"><\/script>');</script><div id=stat-wrap>
<script src="http://s19.cnzz.com/stat.php?id=1252976445&web_id=1252976445" type=text/javascript></script></div></body></html>